package SwordOffer;

public class Sword_Offer_14_II {

    public int cuttingRope(int n) {
        if (n <= 3) {
            return n - 1;
        }
        int mod = n % 3;
        int count = (n - 3) / 3;
        int res = 1;
        for (int i = 0; i < count; i++) {
            res = ((res + res) % 1000000007 + res) % 1000000007;
        }
        if (mod == 0) {
            res = ((res + res) % 1000000007 + res) % 1000000007;
        } else if (mod == 1) {
            res = (res + res) % 1000000007;
            res = (res + res) % 1000000007;
        } else {
            res = ((res + res) % 1000000007 + res) % 1000000007;
            res = (res + res) % 1000000007;
        }
        return res;
    }

    public static void main(String[] args) {
        Sword_Offer_14_II model = new Sword_Offer_14_II();
        System.out.println(model.cuttingRope(1000));
    }
}
